// 给定一个非空的整数数组， 返回其中出现频率前 k 高的元素。
// 提示：
// 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
// 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
// 你可以按任意顺序返回答案。

// 数字索引哈希表接口
interface INumberMap {
    [key: number]: number;
}

// 暴露接口
function topKFrequent(nums: number[], k: number): number[] {
    const hashMap: INumberMap = {};
    // 统计词频
    for (let num of nums) {
        if (hashMap[num]) {
            hashMap[num] += 1;
        } else {
            hashMap[num] = 1;
        }
    }
    return topKFrequent_budgetSort(hashMap, k);
};
// 桶排序部分
function topKFrequent_budgetSort(map: INumberMap, k: number): number[] {
    let budget: number[][] = [];// 桶
    const res: number[] = [];// 结果数组
    Object.keys(map).forEach(index => {// 为桶排序设坑
        let key: number = parseInt(index, 10);// 类型转换
        if (!budget[map[key]]) {// 桶内存的是数组，若未装过数组则初始化
            budget[map[key]] = [key];
        } else {
            budget[map[key]].push(key);// 往桶内的数组直接push
        }
    });
    for (let i = budget.length - 1; i >= 0; i--) {
        if (res.length === k) {// 满足k个的要求则直接跳出循环
            break;
        }
        if (budget[i] != null) res.push(...budget[i]);
    }
    return res;
}


// 这道题目也是一道细节比较多，值得练习的例题
// 首先我们需要使用一个hashMap来统计一下词频
// 统计出词频之后，可以巧妙的使用桶排序来解决TopK的问题
// 桶用一系列的数组表示，而数组的索引 0~n 其实就代表了hashMap统计出的频数
// 数组内存储的是一个数组，数组装载的即代表频数对应的元素，
// 例如说在原数组中，1和3都出现了5次，那么5号桶中装载的数组就是[1,3]
// 桶排序结束之后，我们就拿到了一个相对有序的桶集合
// 我们使用倒序遍历的方式来依次输出桶中的元素，这里也要注意一个细节：
// 部分桶中可能存在的元素是为空的，我们需要跳过这些为空的桶
// 直到输出的结果数组长度与k相等时就得到了最后的结果。

